import java.util.HashMap;
import java.util.Map;

/**
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode.cn/problems/trapping-rain-water/ 42.接雨水
 * @date 2023/2/24
 **/
public class TrappingRainWater {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        // 10
//        int[] height = new int[]{4, 2, 0, 3, 2, 4, 3, 4};
        // 23
//        int[] height = new int[]{5, 5, 1, 7, 1, 1, 5, 2, 7, 6};
        System.out.println(solution.trap(height));
    }

    private static class Solution {

        public int trap(int[] height) {
            if (height == null || height.length <= 1) {
                return 0;
            }
            int sum = 0, lastHeight = -1;
            for (int i = 0; i < height.length; i++) {
                if (lastHeight != -1 && height[i] < lastHeight) {
                    continue;
                }
                if (height[i] == 0) {
                    continue;
                }
                if (i + 1 < height.length && height[i + 1] >= height[i]) {
                    continue;
                }
                int rightIndex = -1, rightMaxHeight = 0;
                for (int j = i + 2; j < height.length; j++) {
                    if (height[j] > rightMaxHeight) {
                        rightMaxHeight = height[j];
                        rightIndex = j;
                    }
                }
                if (rightIndex != -1 && i + 1 < height.length && height[rightIndex] < height[i + 1]) {
                    continue;
                }
                if (rightIndex != -1) {
                    sum += calcArea(height, i, rightIndex, lastHeight);
                    lastHeight = height[i];
                }
            }
            return sum;
        }

        private int calcArea(int[] height, int leftIndex, int rightIndex, int lastHeight) {
            int sum;
            if (lastHeight == -1) {
                sum = (rightIndex - leftIndex - 1) * Math.min(height[leftIndex], height[rightIndex]);
            } else {
                sum = (rightIndex - leftIndex - 1) * (Math.min(height[leftIndex], height[rightIndex]) - lastHeight);
            }
            for (int i = leftIndex + 1; i < rightIndex; i++) {
                if (lastHeight == -1) {
                    sum -= height[i];
                } else {
                    if (height[i] <= lastHeight) {
                        continue;
                    } else {
                        sum -= (height[i] - lastHeight);
                    }
                }
            }
            System.out.println(String.format("leftIndex=%s, rightIndex=%s, sum=%s", leftIndex, rightIndex, sum));
            return sum;
        }
    }
}



